package 剑指offer_leetcode;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * JZ56数组中只出现一次的两个数字
 */
public class 剑指Offer56_I_数组中数字出现的次数 {

    //异或运算
    public int[] singleNumbers(int[] nums) {
        int res1 = 0;
        int res2 = 0;
        int tmp = 0;
        for(int i=0;i<nums.length;i++)
            tmp ^= nums[i];
        int k = 1;
        while((k&tmp) == 0)
            k <<= 1;
        for(int i=0;i<nums.length;i++){
            if( (k&nums[i]) == 0 )
                res1 ^= nums[i];
            else
                res2 ^= nums[i];
        }
        return new int[]{res1,res2};
    }


    //哈希表
    public int[] singleNumbers2(int[] nums) {
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
        ArrayList<Integer> res = new ArrayList<Integer>();

        //遍历数组
        for(int i = 0; i < nums.length; i++)
            //统计每个数出现的频率
            if(!mp.containsKey(nums[i]))
                mp.put(nums[i], 1);
            else
                mp.put(nums[i], mp.get(nums[i]) + 1);

        //再次遍历数组
        for(int i = 0; i < nums.length; i++)
            //找到频率为1的两个数
            if(mp.get(nums[i]) == 1)
                res.add(nums[i]);

        return new int[] {res.get(0), res.get(1)};
    }
}
